package sort;

import java.util.*;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @Description: 七大排序的实现过程
 * @Author Stark
 * @Date 2022/3/17 21:02
 **/
public class SevenSort {
    public static final ThreadLocalRandom random = ThreadLocalRandom.current();
    /**
     * 选择排序
     * @param arr
     */
    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            // min变量存储了当前的最小值索引
            int min = i;
            // 从剩下的元素中选择最小值
            for (int j = i; j < arr.length; j++) {
                if(arr[j] < arr[min]){
                    min = j;
                }
            }
            // min这个索引一定对应了当前无序区间中找到的最小值索引，换到无序区间最前面i
            swap(arr,min,i);
        }
    }
    //双路选择排序
    public static void selectionSortOp(int[] arr){
        int left = 0;
        int right = arr.length - 1;
        // low = high，无序区间只剩下一个元素，整个数组已经有序
        while(left < right){
            int min = left;
            int max = left;
            for (int i = left; i <= right; i++) {
                if(arr[min] > arr[i])
                    min = i;
                if(arr[max] < arr[i])
                    max = i;
            }
            // min索引一定是当前无序区间的最小值索引，与low交换位置
            swap(arr,min,left);
            if(max == left)
                // 最大值已经被换到min这个位置
                max = min;
            swap(arr,max,right);
            left++;
            right--;
        }
    }

    /**
     * 冒泡排序
     * @param arr
     */
    public static void bubbleSort(int[] arr){
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if(arr[j] > arr[j + 1]){
                    swap(arr,j,j + 1);
                }
            }
        }
    }

    /**
     * 插入排序
     * @param arr
     */
    public static void insertSort(int[] arr){
        // 已排序区间[0,i)
        // 待排序区间[i...n]
        for (int i = 0; i < arr.length - 1; i++) {
            // 待排序区间的第一个元素arr[i]
            // 从待排序区间的第一个元素向前看，找到合适的插入位置
            for (int j = i ; j >= 0 && arr[j + 1] < arr[j]; j--) {
                swap(arr,j,j + 1);
            }
        }
    }

    //不交换元素，直接存放
    public static void insertSortOp(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            //比较如果不需要插入则直接进入下次循环
            if(arr[i] > arr[i + 1]){
                int j = i;
                //将需要插入的元素保存
                int tmp = arr[i + 1];
                //寻找合适的位置,这里的j指向需要插入的前一个元素
                for (; j >= 0 && arr[j] > tmp; j--);
                //将该位置和后面已经排好序的元素一次往后移动
                for (int k = i;k > j; k--) {
                    arr[k + 1] = arr[k];
                }
                //将该元素放在该位置上
                arr[j + 1] = tmp;
            }
        }
    }

    //插入排序二分搜索优化版本
    public static void insertSortBS(int[] arr){
        // 有序区间[0..i]
        // 无序区间(i...n]
        for (int i = 0; i < arr.length - 1; i++) {
            if(arr[i + 1] < arr[i]){
                int left = 0;
                int right = i;
                int val = arr[i + 1];
                while(left <= right){
                    int mid = left + ((right - left) >> 1);
                    if(arr[mid] <= val)
                        left = mid + 1;
                    else
                        right = mid - 1;
                }
                // 搬移left..i的元素
                for (int j = i; j >= left; j--) {
                    arr[j + 1] = arr[j];
                }
                // left就是val插入的位置
                arr[left] = val;
            }
        }
    }

    /**
     * 希尔排序
     * @param arr
     */
    public static void shellSort(int[] arr){
        int gap = arr.length >> 1;
        //最后一次循环的gap为1,也就是插入排序了
        while(gap >= 1){
            shellSortHelper(arr,gap);
            //减小间距gap
            gap >>= 1;
        }
    }

    private static void shellSortHelper(int[] arr, int gap) {
        //可以看出这个结构就是插入排序,只是比较元素的间隔变化而已
        for (int i = 0; i < arr.length - gap; i++) {
            for (int j = i; j >= 0 && arr[j + gap] < arr[j]; j-=gap) {
                swap(arr,j,j+gap);
            }
        }
    }

    /**
     * 归并排序，写法一
     * 每次归并时开辟临时数组
     * @param arr
     */
    public static void mergeSortVersion1(int[] arr){
        mergerSort2(arr,0,arr.length - 1);
    }

    private static void mergerSort2(int[] arr, int left, int right) {
        if(right - left <= 15){
            // 小区间直接使用插入排序
            insertSortRange(arr,left,right);
            return;
        }
        int mid = left + ((right - left) >> 1);
        // 将原数组拆分为左右两个小区间，分别递归进行归并排序
        // 走完这个函数之后 arr[l..mid]已经有序
        mergerSort2(arr,left,mid);
        // 走完这个函数之后 arr[mid + 1..r]已经有序
        mergerSort2(arr,mid + 1,right);
        if(arr[mid] > arr[mid + 1]) {
            //只有左右两个子区间还有先后顺序不同时才merge
            merge1(arr, left, mid, right);
        }
    }

    private static void merge1(int[] arr, int left, int mid, int right) {
        // 先创建一个新的临时数组tmp
        int[] tmp = new int[right - left + 1];
        // 将arr元素值拷贝到tmp上
        for (int i = 0; i < tmp.length; i++) {
            tmp[i] = arr[left + i];
        }
        // l1就是左侧小数组的开始索引
        int l1 = left;
        // l2就是右侧小数组的开始索引
        int l2 = mid + 1;
        // i表示当前正在合并的原数组的索引下标
        for(int i = left;i <= right; i++){
            if(l1 > mid){
                // 左侧区间已经被处理完毕，只需要将右侧区间的值拷贝原数组即可
                arr[i] = tmp[l2 - left];
                l2++;
            }else if(l2 > right){
                // 右侧区间已经被处理完毕，只需要将左侧区间的值拷贝到原数组即可
                arr[i] = tmp[l1 - left];
                l1++;
            }else if(tmp[l1 - left] <= tmp[l2 - left]){
                // 此时左侧区间的元素值较小，相等元素放在左区间，保证稳定性
                arr[i] = tmp[l1 - left];
                l1++;
            }else{
                // 右侧区间的元素值较小
                arr[i] = tmp[l2 - left];
                l2++;
            }
        }
    }

    private static void insertSortRange(int[] arr, int left, int right) {
        for (int i = left; i < right; i++) {
            //比较如果不需要插入则直接进入下次循环
            if(arr[i] > arr[i + 1]){
                int j = i;
                //将需要插入的元素保存
                int tmp = arr[i + 1];
                //寻找合适的位置,这里的j指向需要插入的前一个元素
                for (; j >= left && arr[j] > tmp; j--);
                //将该位置和后面已经排好序的元素一次往后移动
                for (int k = i;k > j; k--) {
                    arr[k + 1] = arr[k];
                }
                //将该元素放在该位置上
                arr[j + 1] = tmp;
            }
        }
    }

    /**
     * 归并排序，写法二
     * 在一开始就定义和原数组一样大的空间
     * @param arr
     */
    public static void mergeSortVersion2(int[] arr) {
        int[] temp = new int[arr.length];//额外的辅助空间
        mergeSortHelper2(arr, 0, arr.length - 1, temp);
    }

    private static void mergeSortHelper2(int[] arr, int left, int right, int[] temp) {
        if(right - left  <= 15) {
            insertSortRange(arr,left,right);
            return;
        }
        int mid = left + ((right - left) >> 1);
        mergeSortHelper2(arr,left,mid,temp);
        mergeSortHelper2(arr,mid + 1,right,temp);
        //当arr[mid]<arr[mid + 1]时,这个小区间已经有序了,就不需要再排序了
        if(arr[mid] > arr[mid + 1]) {
            merge2(arr, left, mid, right, temp);
        }
    }

    private static void merge2(int[] arr, int left, int mid, int right, int[] temp) {
        int l1 = left;
        int l2 = mid + 1;
        int index = left;
        //循环比较数组元素，将其写到辅助数组对应空间上
        //当左右区间有一边元素完成排序就跳出循环
        while(l1 <= mid && l2 <= right){
            if(arr[l1] <= arr[l2]){
                temp[index++] = arr[l1++];
            }else{
                temp[index++] = arr[l2++];
            }
        }
        //左区间还有元素,而且不需要排序,直接写到辅助空间上
        while(l1 <= mid){
            temp[index++] = arr[l1++];
        }
        //右区间还有元素
        while(l2 <= right){
            temp[index++] = arr[l2++];
        }
        //将排序完的元素写回原数组中
        for (int i = left; i <= right; i++) {
            arr[i] = temp[i];
        }
    }

    /**
     * 归并排序的非递归
     * @param arr
     */
    public static void mergeSortNonRecursion(int[] arr){
        int[] tmp = new int[arr.length];
        for (int gap = 1; gap < arr.length; gap <<= 1) {
            // 内层循环的变量i表示每次合并的开始索引
            // i + gap 就是右区间的开始索引，i + gap < arr.length说明还存在右区间
            for (int i = 0; i + gap< arr.length; i += gap * 2) {
                merge2(arr,i,i + gap - 1,Math.min(i + 2 * gap - 1,arr.length - 1),tmp);
            }
        }
    }

    /**
     * 快速排序
     * @param arr
     */
    public static void quickSort(int[] arr){
        quickSortInternal(arr,0,arr.length - 1);
    }

    private static void quickSortInternal(int[] arr, int left, int right) {
        if(right - left <= 15){
            insertSortRange(arr, left, right);
            return;
        }
//        if(left >= right)
//            return;
        // 先获取分区点
        // 所谓的分区点就是经过分区函数后，某个元素落在了最终的位置
        // 分区点左侧全都是小于该元素的区间，分区点右侧全都是 >= 该元素的区间
        int mid = partition2(arr,left,right);
        // 重复在左区间和右区间上重复上述流程
        quickSortInternal(arr,left,mid - 1);
        quickSortInternal(arr,mid + 1,right);
    }

    //三数取中
    public static int getMiddleIndex(int[] arr,int left,int right){
        int midIndex = ((right - left) >> 1) + left;
        if(arr[left] > arr[midIndex]){
            if(arr[midIndex] > arr[right]) {
                return midIndex;
            }
            else if(arr[left] < arr[right]) {
                return left;
            }
            else {
                return right;
            }
        }else{
            if(arr[left] > arr[right]) {
                return left;
            }
            else if(arr[midIndex] > arr[right]) {
                return right;
            }
            else {
                return midIndex;
            }
        }
    }

    //单路快排
    //在分区上从前往后找分区点
    private static int partition1(int[] arr, int left, int right) {
        int randomIndex = random.nextInt(left,right);
        swap(arr,left,randomIndex);
//        int middleIndex = getMiddleIndex(arr,left,right);
//        swap(arr,left,middleIndex);
        //基准值
        int v = arr[left];
        int mid = left;
        for (int i = left + 1; i <= right; i++) {
            //只交换小于基准值的数
            //[left+1,mid] < v
            //[mid+1,i] <= v
            //[i+1,right]还为排序
            if(arr[i] < v){
                swap(arr,mid + 1,i);
                mid++;
            }
        }
        //把基准值和最后一个 < 0的值交换,就处在了最终的位置上
        swap(arr,left,mid);
        return mid;
    }

    //双路快排，将和基准值相等的值分在两边，不至于失衡
    //当数组中存在大量相同的元素时,又会退化为单只树时效率又会退化
    //跟挖坑法差别不大，挖坑法是将坑位赋值
    //双路快排,是交换>=v和<=v的值
    private static int partition2(int[] arr,int left,int right){
        int randomIndex = random.nextInt(left,right);
        swap(arr,left,randomIndex);
        int v = arr[left];
        int i = left + 1;
        int j = right;
        while(true){
            // i从前向后扫描，碰到第一个 >= v的元素停止
            while(i <= j && arr[i] < v)
                i++;
            // j从后向前扫描，碰到第一个 <= v的元素停止
            while(i <= j && arr[j] > v)
                j--;
            if(i >= j){
                break;
            }
            swap(arr,i,j);
            i++;
            j--;
        }
        // j落在最后一个 <= v的元素身上
        swap(arr,j,left);
        return j;
    }

    public static void quickSort2(int[] arr){
        quickSortInternal2(arr,0,arr.length - 1);
    }
    //三路快排，将相等的值放在固定位置上,不参与排序
    //只需要处理不等于参考值的数据
    //有大量相同值时可以考虑
    private static void quickSortInternal2(int[] arr,int left,int right){
        if(right - left <= 15){
            insertSortRange(arr,left,right);
            return;
        }
        int randomIndex = random.nextInt(left,right);
        swap(arr,left,randomIndex);
        int v = arr[left];
        // 这些变量的取值，一定是满足区间的定义，最开始的时候，所有区间都是空
        // arr[left + 1..lt] < v
        // lt是指向最后一个<v的元素
        int lt = left;
        // arr[gt..right] > v
        // gt是第一个 > v的元素
        int gt = right + 1;
        // arr[lt + 1..i) == v
        // i - 1是最后一个 = v的元素
        int i = left + 1;
        // i从前向后扫描和gt重合时，所有元素就处理完毕
        while(i < gt){
            if(arr[i] > v){
                // 交换到gt - 1
                swap(arr,i,gt - 1);
                gt--;
                // 此处i不++，交换来的gt - 1还没有处理
            }else if(arr[i] < v){
                // arr[left + 1..lt] < v
                // arr[lt + 1..i) == v
                swap(arr,lt + 1,i);
                lt++;
                i++;
            }else{
                // 此时arr[i] = v
                i++;
            }
        }
        // lt落在最后一个 < v的索引处
        swap(arr,lt,left);
        // arr[l..lt - 1] < v
        quickSortInternal2(arr,left,lt - 1);
        // arr[gt..r] > v
        quickSortInternal2(arr,gt,right);
    }

    //挖坑法
    private static int partition4(int[] arr,int left,int right){
        int randomIndex = random.nextInt(left,right);
        swap(arr,left,randomIndex);
//        int middleIndex = getMiddleIndex(arr,left,right);
//        swap(arr,left,middleIndex);
        //取基准值
        int pivot = arr[left];
        int i = left;
        int j = right;
        while(i < j){
            //从后往前找小于pivot的元素
            while(i < j && arr[j] >= pivot){
                j--;
            }
            //将这个元素放入坑位中
            arr[i] = arr[j];
            //从前往后找大于pivot的元素
            while(i < j && arr[i] <= pivot){
                i++;
            }
            //再将这个元素放入坑位中
            arr[j] = arr[i];
        }
        //将基准值填入坑位中
        arr[i] = pivot;
        return i;
    }

    //前后指针法
    private static int partition5(int[] arr,int left,int right){
        int randomIndex = random.nextInt(left,right);
        swap(arr,left,randomIndex);
        int start = left;
        int end = right;
        int key = arr[left];
        while (start < end)
        {
            //从右向左找比key小的值,找到后就停下
            while (start < end && arr[end] >= key)
                end--;
            //从左往右找比key大的值,找到后就停下
            while (start < end && arr[start] <= key)
                start++;
            //交换两值
            swap(arr,start,end);
        }
        //执行完循环后,将key和指针相遇的地方交换
        swap(arr,start, left);
        return start;//返回前后指针相遇的地方
    }

    // 快速排序快慢指针法
    private static int partition6(int[] arr, int left, int right)
    {
        int mid = getMiddleIndex(arr, left, right);//三数取中
        swap(arr,left,mid);//将该数默认放在最左边
        int key = arr[left];
        int fast = left + 1;//初始化快指针
        int slow = left;//慢指针
        while (fast <= right)
        {
            //如果有值小于key并且快慢指针不指向同一块地方就交换值
            if (arr[fast] < key && ++slow != fast)
            {
                swap(arr,slow,fast);
            }
            fast++;
        }
        swap(arr,left, slow);
        return slow;
    }



    public static void quickSortNonRecursion(int[] arr){
        // 栈中保存当前集合的开始位置和终止位置
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(arr.length - 1);
        stack.push(0);
        while(!stack.isEmpty()){
            // 栈不为空时，说明子区间还没有处理完毕
            int left = stack.pop();
            int right = stack.pop();
            int mid = partition2(arr,left,right);
            if(left < mid - 1) {
                // 依次将左区间的开始和结束位置入栈
                stack.push(mid - 1);
                stack.push(left);
            }
            if(mid + 1 < right) {
                // 依次将右区间的开始和结束位置入栈
                stack.push(right);
                stack.push(mid + 1);
            }
        }
    }

    public static void heapSort(int[] arr){
        // 先将arr进行heapify调整为最大堆
        // 从最后一个非叶子节点开始进行siftDown操作
        for (int i = (arr.length - 1 - 1) >> 1; i >= 0; i--) {
            siftDown(arr,i,arr.length);
        }
        // 此时arr就被我调整为最大堆
        for (int i = arr.length - 1; i >= 0; i--) {
            // arr[0] 堆顶元素，就是当前堆的最大值
            swap(arr,i,0);
            siftDown(arr,0,i);
        }
    }

    /**
     * 元素下沉操作
     * @param arr
     * @param i 当前要下沉的索引
     * @param length 数组长度
     */
    private static void siftDown(int[] arr, int i,int length) {
        int child = 2 * i + 1;
        if (child >= length) {
            return;
        }
        if (child + 1 < length && arr[child + 1] > arr[child]) {
            child++;
        }
        //child就是左子树最大的索引
        if (arr[i] < arr[child]) {
            swap(arr,i,child);
        }
        //将子结点赋值给需要下沉的索引，向下递归，直到下沉完毕
        i = child;
        siftDown(arr,i,length);
    }

    private static void swap ( int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
